#include <vector>
#include <map>
#include <iostream>
using namespace std;

// template <class T>
// class UnionFindSet{
//     vector<T> _vct; //编号找人
//     map<T, int> _map; //人找编号
//     vector<int> _ufs; //并查集s
// public:
//     UnionFindSet(const T* set, int n)
//     {
//         //1.建立编号<-->人名的映射关系
//         for(int i = 0; i < n; ++i)
//         {
//             _vct.push_back(set[i]);
//             _map[set[i]] = i;
//         }
//         //2.初始化并查集
//         _ufs.resize(n, -1); //初始时，每个元素自成一个单元素集合
//     }
// };

// 假设只有编号，实现一个简单的并查集
class UnionFindSet{
    vector<int> _ufs; //并查集s

public:
    UnionFindSet(int n)
    {
        _ufs.resize(n, -1); //初始时，每个元素自成一个单元素集合
    }

    bool Union(int x, int y)
    {
        int rx = FindRoot(x);
        int ry = FindRoot(y);
        if(rx == ry) return false;
        // 数据量小的集合向大集合中合并
        if(_ufs[rx] > _ufs[ry])
            swap(rx, ry);
        _ufs[rx] += _ufs[ry];
        _ufs[ry] = rx;
        return true;
    }

    int FindRoot(int x)
    {
        int root = x;
        while(_ufs[root] >= 0)
        {
            root = _ufs[root];
        }

        // 路径压缩
        while(_ufs[x] >= 0)
        {
            int parent = _ufs[x];
            _ufs[x] = root;
            x = parent;
        }

        return root;
    }

    bool InSet(int x, int y)
    {
        return FindRoot(x)==FindRoot(y);
    }

    int SetCount()
    {
        int count = 0;
        for(int e : _ufs)
        {
            if(e < 0) ++count;
        }
        return count;
    }
};